package 剑指Offer;

public class Offer14II_剪绳子II {
    public int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }
        //注意这里要用long，不可用int，不然n=120的时候就会报错了
        long res = 1;
        while (n > 4) {
            res = res * 3 % 1000000007;
            n = n - 3;
        }

        return (int) (res * n % 1000000007);
    }
}
